/*
 * @lc app=leetcode id=460 lang=cpp
 *
 * [460] LFU Cache
 */

// @lc code=start
#include <sys/types.h>
class LFUCache {
public:
    struct Node {
        int key;
        int val;
        int freq;
        Node(int _key, int _val, int _freq): key(_key), val(_val), freq(_freq) {
        }

    }
    LFUCache(int capacity) {        
        capacity_ = capacity;
    }
    
    int get(int key) {
        auto iter = key_table_.find(key);
        if (iter == key_table_.end()){
            return -1;
        }
        int val = iter->val;
        int freq =iter->freq;
        freq_map_[freq].erase(*iter);
        if (freq_map_[freq].empty()){
            freq_map_.erase(freq);
            if (freq == min_freq_) {
                min_freq_ = freq + 1;
            }
        }
        freq_map_[freq+1].push_front(Node(key, val, freq+1));
        key_table_[key] = freq_map_[freq+1].begin();
        return  val;        
    }
    
    void put(int key, int value) {
        if (capacity_ == 0) {
            return ;
        }
        auto iter = key_table_.find(key);
        if (iter == key_table_.end()){
            if (capacity_ == key_table_.size()){
                auto node = freq_map_[min_freq_].back();
                freq_map_[min_freq_].pop_bakc();
                key_table_.earse(node->key);
                if (freq_map_[min_freq_].empty()) {
                    freq_map_.erase(min_freq_);
                }
            }
             min_freq_ = 1;
            freq_map_[1].push_front(Node(key, value, 1));
            key_table_[key] = freq_map_[1].begin();   
                
        } else {
            int freq = iter->freq;
            freq_map_[freq].earse(*iter);
            if (freq_map_[freq].empty()){
                freq_map_.earse(freq);
                if (freq == min_freq_){
                    min_freq_ = freq+1;
                }
            }
            freq_map_[freq + 1].push_front(Node(key, value, freq+1));
            key_table_[freq+1] = freq_map_[freq + 1].begin();

        }

        
    }
    int capacity_;
    int min_freq_ = 0;
    unordered_map<int, std::list<Node>::const_iterator> key_table_;
    unordered_map<int, std::list<Node>> freq_map_;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end

